#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <iterator>

void swap(int a[], int i, int j) {
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}
void quicksort(int a[], int left, int right) { //left as pivot
	if(left >= right) return;
	int last = left+1;
	for( int i = left+1; i <= right; i++) {
		if(a[i] < a[left]) 
			swap(a,i,last++);
	}
	swap(a,left,last-1);
	quicksort(a,left,last-2);
	quicksort(a,last,right);
}

void quicksort_right_pivot(int a[], int left, int right) { //right as pivot
	if(left >= right) return;
	int last = left;
	for (int i = left; i < right; i++) 
		if( a[i] < a[right] )
			swap(a,i,last++);
	swap(a,last,right);
	quicksort_right_pivot(a,left,last-1);
	quicksort_right_pivot(a,last+1,right);
}

int partition(int a[], int left, int right){
	int pivot = a[(left+right)/2];
	while (left < right) {
		while (a[left] < pivot)
			++left;
		while (a[right] > pivot)
			--right;
		if (left < right) 
			swap(a,left++,right--);
	}
	return left;
}
void quicksort_2(int a[], int left, int right) {
	if (left < right) {
		int pivot_index  = partition(a, left, right);
		quicksort_2(a, left, pivot_index-1);
		quicksort_2(a, pivot_index+1, right);
	}
}

void test_quicksort_2(){
	int a[] = {5,4,3,2};
	int n = sizeof(a)/sizeof(int);
	quicksort_2(a,0,n-1);
	std::copy(a,a+n,std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl;
}
	

void build_random_array(int a[], int size, unsigned int range) {
	srand(time(NULL));
	for(int i = 0; i < size; i++) {
		a[i] = rand() % range;
	}
}